package LinkedList;

import Node.ListNode;

import java.util.PriorityQueue;

/**
 * 合并k个单链表
 */
public class MergeKList {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0)
            return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                lists.length, (a, b) -> (a.val - b.val)
        );
        // 将k个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null) {
                pq.add(head);
            }
        }

        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            p.next = node;
            if (p.next != null) {
                pq.add(p.next);
            }

            // p指针前进
            p = p.next;
        }
        return dummy.next;
    }
}
